
public class MedianOfTwoSortedArrays {
	public void tester()
	{
		int [] a = {1};
		int [] b = {2,3};
		System.out.println(fmsa2(a,b));
	}
	
	public double fmsa2(int A[], int B[]) {
        if(A.length > B.length) return fmsa2(B, A);
        
        int total = A.length + B.length;
        if(total %2 == 1) total ++;
        
        int i = (A.length-1)/2;
        int j = total/2-i;
        
        int low = 0, high = A.length ;
        
        while(low < high)
        {
            if(i>0 && j<B.length && B[j]<A[i-1])
                high = i -1;
            else if(j>0 && i<A.length && A[i]<B[j-1])
                low = i+1;
            else
            {
                break;
            }
            
            i = low+(high-low)/2;
            j = total/2-i;
        }
        
        System.out.println(i+" "+j);
        
        double result1 = 0;
        
        if(i == 0) result1 = (double)B[j-1];
        else if(j == 0) result1 = (double)A[i-1];
        else result1 = (double)max(A[i-1],B[j-1]);
        
        if((A.length + B.length)%2==1) return result1;
        
        double result2 = 0;
        
        if(j >= B.length) result2 = (double)A[i];
        else if(i >= A.length) result2 = (double)B[j];
        else result2 = (double)min(A[i], B[j]);
        
        return (result1+result2)/2.0;
    }
	
	public double fmsa(int A[], int B[]) {
		int m = A.length;
		int n = B.length;
		
		if(m>n)
			return fmsa(B,A);
		
		int imin = 0, imax = m;
		
		while(imin <= imax)
		{
			int i = (imin + imax) /2;
			int j = ((m+n+1)/2) - i;
			if(j>0 && i<m && B[j-1]>A[i])
				imin = i+1;
			else if(i>0 && j<n && A[i-1]>B[j])
				imax = i-1;
			else
			{
				System.out.println(i+" "+j);
				
				int num1 = 0;
				if(i == 0)
					num1 = B[j-1];
				else if(j == 0)
					num1 = A[i-1];
				else
					num1 = max(A[i-1], B[j-1]);
				
				if((m+n)%2==1)
					return num1;
				
				int num2 = 0;
				if(i == m)
					num2 = B[j];
				else if(j == n)
					num2 = A[i];
				else
					num2 = min(A[i], B[j]);
				
				return (num1 + num2) / 2.0;
				
			}
		}
		
		return 0;
	}
	
	public int max(int a, int b)
	{
		if(a>b) return a;
		else return b;
	}
	
	public int min(int a, int b)
	{
		if(a>b) return b;
		else return a;
	}
	
	public double findMedianSortedArrays(int A[], int B[]) {
        int a1 = 0, a2 = A.length - 1;
        int b1 = 0, b2 = B.length - 1;
        
        int len = 0;
        if(A.length > B.length) len = B.length;
        else len = A.length;
        
        int total = A.length + B.length;
        
        int ta = A[(a1+a2)/2];
        int tb = B[(b1+b2)/2];
        
        while(len > 1)
        {
            if(a1+a2>=2 && tb < A[(a1+a2)/2-1])
            {
                a2 = a2 - len/2;
                b1 = b1 + len/2;
                len = len - len /2;
            }
            else if(b1+b2>=2 && ta < B[(b1+b2)/2-1])
            {
                a1 = a1 + len/2;
                b2 = b2 - len/2;
                len = len/2;
            }
            else
            {
                break;
            }
            
            ta = A[(a1+a2)/2];
            tb = B[(b1+b2)/2];
        }
        
        System.out.println("ta: "+ta+" tb: "+tb);
        
        if(total%2==1)
        {
        	int index1 = 0, index2 = 0;
        	
        	if(a1+a2<2) index1 = 0;
        	else index1 = (a1+a2)/2;
        	
        	if(b1+b2<2) index2 = 0;
        	else index2 = (b1+b2)/2;
        	
            if(A[index1] > B[index2]) return (double)A[index1];
            else return (double)B[index2];
        }
        else
        {
            
        }
        
        return Double.MAX_VALUE;
    }
	
	
    public double findMedianSortedArrays3(int A[], int B[]) {
        
        
        
        
        return 0;
    }
    
    public static int rank(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }
    
    public int binarySearch(int [] a, int k)
    {
    	int low = 0;
    	int high = a.length - 1;
    	
    	while(low <= high)
    	{
    		int mid = low + (high - low)/2;
    		if(k < a[mid])
    			high = mid - 1;
    		else if(k > a[mid])
    			low = mid + 1;
    		else
    			return mid;
    	}
    	return -1;
    }
    
    public double findMedianSortedArrays2(int A[], int B[]) {
        int a1 = 0, a2 = A.length - 1;
        int b1 = 0, b2 = B.length - 1;
        
        int len = 0;
        if(A.length > B.length) len = B.length;
        else len = A.length;
        
        int total = A.length + B.length;
        
        int ta = A[(a1+a2)/2];
        int tb = B[(b1+b2)/2];
        
        while(len > 1)
        {
            if(ta > tb)
            {
                a2 = a2 - len/2;
                b1 = b1 + len/2;
                len = len - len /2;
            }
            else if(ta < tb)
            {
                a1 = a1 + len/2;
                b2 = b2 - len/2;
                len = len/2;
            }
            else
            {
                break;
            }
            
            ta = A[(a1+a2)/2];
            tb = B[(b1+b2)/2];
        }
        
        if(a1 == a2 && b1 != b2)
        {
            
        }
        
        
        if(A.length %2 == 0 && B.length % 2 == 0)
        {
            int [] array = new int [4];
            array[0] = ta;
            array[1] = tb;
            if(A.length > B.length && A.length > 2)
            {
                array[2] = A[(a1+a2)/2 + 1];
                array[2] = A[(a1+a2)/2 - 1];
            }
            else if(A.length < B.length && B.length > 2)
            {
                array[2] = B[(b1+b2)/2 + 1];
                array[2] = B[(b1+b2)/2 - 1];
            }
            else if(A.length == B.length)
            {
                
            }
        }
        else
        {
            if(a1 == a2)
            {
                
            }
            else if(b1 == b2)
            {
                
            }
        }
        
        return Double.MAX_VALUE;
    }
}